最值型问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

动态规划的本质：它是一种 “以空间换时间”的优化算法，核心是把复杂问题拆解为多个重叠的子问题，通过记录子问题的最优解（状态），避免重复计算，最终由子问题的最优解推导出原问题的最优解。

算法回顾

动态规划的适用有三个核心前提（缺一不可），这也是判断一个问题是否能用 DP 解决的关键：
- 最优子结构：原问题的最优解包含其子问题的最优解；
- 重叠子问题：求解原问题时，会反复遇到相同的子问题（这是 DP 能优化的基础，否则不如暴力递归）；
- 无后效性：某一阶段的状态确定后，后续的状态推导只依赖当前状态，与状态的形成过程无关。

最值型问题

最值型问题是动态规划的入门级也是最核心的应用，核心需求是求问题的最优解（最大 / 最小 / 最长 / 最短），比如最长子序列、最大和、最小花费、最短路径等。这类问题的暴力解法通常是递归枚举所有可能，存在大量重叠子问题，DP 通过记录子问题的最值，直接推导原问题最值。

核心解题思路
- 定义状态：明确dp[i]/dp[i][j]的含义（如dp[i]表示 “以第 i 个元素结尾的最优解”）；
- 确定初始状态：找到问题的边界情况，初始化基础子问题的解（如dp[0]/dp[0][0]）；
- 推导状态转移方程：明确 “当前状态如何由前面的状态推导而来”（如dp[i] = max(dp[i-1]+nums[i], nums[i])）；
- 确定结果：根据状态定义，从 dp 数组中提取原问题的最优解（如max(dp)/dp[n-1]）。

典型例题
- 最大子数组和（LeetCode 53）：找数组中和最大的连续子数组（一维 DP）；
- 最长递增子序列（LeetCode 300）：找数组中最长的严格递增子序列（一维 DP）；
- 最长公共子序列（LeetCode 1143）：找两个字符串的最长公共子序列（二维 DP）；
- 最小路径和（LeetCode 64）：从二维网格左上角到右下角，找路径和最小的路径（二维 DP）；
- 爬楼梯（LeetCode 70）：每次爬 1/2 阶，求爬到第 n 阶的最小 / 总方法数（一维 DP，计数型也属于此类延伸）。

教程目录导航

▼

最值型问题

一、最大子数组和（LeetCode 53）

问题描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
- 子数组是数组中的一个连续部分。
提示：
- 1 <= nums.length <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
示例 1：
- 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
- 输出：6
- 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
- 输入：nums = [5,4,-1,7,8]
- 输出：23

算法解析：

确定状态：定义 dp[i] 表示以数组第 i 个元素结尾的连续子数组的最大和。
状态转移方程：dp[i] = max( nums[i], dp[i−1] + nums[i] )
初始化：dp[0] = nums[0]（第一个元素的最大子数组和就是自身）。
遍历顺序：从左到右（i 从 1 到 n）。
结果：遍历整个 dp 数组，取最大值即为答案。

dp 数组计算过程：

输入数组：[-2,1,-3,4,-1,2,1,-5,4]

dp[0] = -2
dp[1] = max(1, -2+1) = max(1, -1) = 1
dp[2] = max(-3, 1-3) = max(-3, -2) = -2
dp[3] = max(4, -2+4) = max(4, 2) = 4
dp[4] = max(-1, 4-1) = max(-1, 3) = 3
dp[5] = max(2, 3+2) = max(2, 5) = 5
dp[6] = max(1, 5+1) = max(1, 6) = 6
dp[7] = max(-5, 6-5) = max(-5, 1) = 1
dp[8] = max(4, 1+4) = max(4, 5) = 5


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int maxSubArray(vector<int>& nums) {
    // 处理边界情况
    if (nums.empty()) return 0;

    int n = nums.size();
    // 定义 dp 数组，dp[i] 表示以 nums[i] 结尾的最大子数组和
    vector<int> dp(n);

    // 初始化 dp 数组第一个元素
    dp[0] = nums[0];

    // 填充 dp 数组
    for (int i = 1; i < n; ++i) {
        // 状态转移：要么重新开始，要么加入前一个子数组
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
    }

    // 遍历 dp 数组，找到最大值（即全局最大子数组和）
    int max_sum = dp[0];
    for (int val : dp) {
        max_sum = max(max_sum, val);
    }

    return max_sum;
}

int main() {
    // 测试用例1：输出 6
    vector<int> nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Test Case 1: " << maxSubArray(nums1) << endl;

    // 测试用例2：输出 1
    vector<int> nums2 = {1};
    cout << "Test Case 2: " << maxSubArray(nums2) << endl;

    // 测试用例3：输出 23
    vector<int> nums3 = {5, 4, -1, 7, 8};
    cout << "Test Case 3: " << maxSubArray(nums3) << endl;

    return 0;
}

输出结果


Test Case 1: 6
Test Case 2: 1
Test Case 3: 23

二、最长递增子序列（LeetCode 300）

问题描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
- 子序列是由数组派生而来的序列，删除数组中的元素不会改变其余元素的顺序。例如，[0,3,6,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
- 严格递增子序列中后一个元素必须大于前一个
提示：
- 1 <= nums.length <= 2500
- -10⁴ <= nums[i] <= 10⁴
示例 1：
- 输入：nums = [10,9,2,5,3,7,101,18]
- 输出：4
- 解释：最长递增子序列是 [2,3,7,101] 或 [2,3,7,18]，因此长度为 4 。
示例 2：
- 输入：nums = [0,1,0,3,2,3]
- 输出：4
示例 3：
- 输入：nums = [7,7,7,7,7,7,7]
- 输出：1

算法解析：

确定状态：定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
状态转移方程：
- 如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 后面形成更长的递增子序列，此时 dp[i] = max(dp[i], dp[j] + 1)；
- 如果 nums[j] >= nums[i]，则跳过。
初始化：每个 dp[i] 初始值为 1（每个元素自身就是长度为 1 的递增子序列）。
遍历顺序：从左到右（i 从 1 到 n）。
结果：遍历整个 dp 数组，取最大值即为答案。

dp 数组计算过程：

输入数组：[10,9,2,5,3,7,101,18]

dp[0] = 1
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 2
dp[5] = 3
dp[6] = 4
dp[7] = 4


#include <iostream>
#include <vector>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;

    int n = nums.size();
    vector<int> dp(n, 1); // 初始化每个位置的最长子序列长度为1
    int max_len = 1;      // 记录全局最大值

    for (int i = 1; i < n; ++i) {
        // 遍历i之前的所有元素，寻找可以接在后面的递增序列
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        // 更新全局最长长度
        max_len = max(max_len, dp[i]);
    }

    return max_len;
}

int main() {
    // 测试用例1：输出 4（最长子序列是 [10,9,2,5,3,7,101,18] 中的 [2,3,7,101]）
    vector<int> nums1 = {10,9,2,5,3,7,101,18};
    cout << "Test Case 1: " << lengthOfLIS(nums1) << endl;

    // 测试用例2：输出 4
    vector<int> nums2 = {0,1,0,3,2,3};
    cout << "Test Case 2: " << lengthOfLIS(nums2) << endl;

    // 测试用例3：输出 1
    vector<int> nums3 = {7,7,7,7,7,7,7};
    cout << "Test Case 3: " << lengthOfLIS(nums3) << endl;

    return 0;
}

输出结果


Test Case 1: 4
Test Case 2: 4
Test Case 3: 1

三、最长公共子序列（LeetCode 1143）

问题描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
- 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
- 两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
提示：
- 1 <= text1.length, text2.length <= 1000
- text1 和 text2 仅由小写英文字符组成。
示例 1：
- 输入：text1 = "abcde", text2 = "ace"
- 输出：3
- 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
- 输入：text1 = "abc", text2 = "abc"
- 输出：3
- 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
- 输入：text1 = "abc", text2 = "def"
- 输出：0
- 解释：两个字符串没有公共子序列，返回 0 。

算法解析：

确定状态：定义 dp[i][j] 表示：text1 的前 i 个字符（text1[0..i-1]）和 text2 的前 j 个字符（text2[0..j-1]）的最长公共子序列长度。
状态转移方程：
- 当 text1[i-1] == text2[j-1]：两个字符匹配，说明可以在 dp[i-1][j-1] 的基础上延长 1，即 dp[i][j] = dp[i-1][j-1] + 1。
- 当 text1[i-1] != text2[j-1]：取 “text1 前 i-1 个字符和 text2 前 j 个字符” 或 “text1 前 i 个字符和 text2 前 j-1 个字符” 的最大值，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始化：
- dp[0][j] = 0（text1 为空，无论 text2 多长，公共子序列长度为 0）。
- dp[i][0] = 0（text2 为空，无论 text1 多长，公共子序列长度为 0）。
遍历顺序：从左到右（i 从 1 到 n）。
结果：最终 dp[len(text1)][len(text2)] 就是两个字符串的最长公共子序列长度。

dp 数组计算过程：

输入：text1 = "abcde"（m=5），text2 = "ace"（n=3）

i=1（text1[0] = 'a'）：
- j=1（text2 [0] = 'a'）：匹配 → dp [1][1] = dp [0][0]+1 = 1
- j=2（text2 [1] = 'c'）：不匹配 → dp [1][2] = max (dp [0][2], dp [1][1]) = 1
- j=3（text2 [2] = 'e'）：不匹配 → dp [1][3] = max (dp [0][3], dp [1][2]) = 1
i=2（text1[1] = 'b'）：
- j=1：不匹配 → dp [2][1] = max (dp [1][1], dp [2][0]) = 1
- j=2：不匹配 → dp [2][2] = max (dp [1][2], dp [2][1]) = 1
- j=3：不匹配 → dp [2][3] = max (dp [1][3], dp [2][2]) = 1
i=3（text1[2] = 'c'）：
- j=1：不匹配 → dp [3][1] = max (dp [2][1], dp [3][0]) = 1
- j=2（text2 [1] = 'c'）：匹配 → dp [3][2] = dp [2][1]+1 = 2
- j=3：不匹配 → dp [3][3] = max (dp [2][3], dp [3][2]) = 2
i=4（text1[3] = 'd'）：
- j=1：不匹配 → dp [4][1] = 1
- j=2：不匹配 → dp [4][2] = max (dp [3][2], dp [4][1]) = 2
- j=3：不匹配 → dp [4][3] = max (dp [3][3], dp [4][2]) = 2
i=5（text1[4] = 'e'）：
- j=1：不匹配 → dp [5][1] = 1
- j=2：不匹配 → dp [5][2] = max (dp [4][2], dp [5][1]) = 2
- j=3（text2 [2] = 'e'）：匹配 → dp [5][3] = dp [4][2]+1 = 3


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();

    // 定义二维DP数组，dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 填充DP数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i-1] == text2[j-1]) {
                // 字符匹配，继承左上角值+1
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                // 字符不匹配，取左边或上边的最大值
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    // 测试用例1：输出 3
    string text1_1 = "abcde";
    string text2_1 = "ace";
    cout << "Test Case 1: " << longestCommonSubsequence(text1_1, text2_1) << endl;

    // 测试用例2：输出 0
    string text1_2 = "abc";
    string text2_2 = "def";
    cout << "Test Case 2: " << longestCommonSubsequence(text1_2, text2_2) << endl;

    // 测试用例3：输出 4
    string text1_3 = "abcba";
    string text2_3 = "abcbcba";
    cout << "Test Case 3: " << longestCommonSubsequence(text1_3, text2_3) << endl;

    return 0;
}

输出结果


Test Case 1: 3
Test Case 2: 0
Test Case 3: 5

四、最小路径和（LeetCode 64）

问题描述：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
- 说明：每次只能向下或者向右移动一步。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
示例 1：
- 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
- 输出：7
- 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
- 输入：grid = [[1,2,3],[4,5,6]]
- 输出：12

算法解析：

确定状态：定义 dp[i][j] 表示：从网格左上角 (0,0) 走到位置 (i,j) 的最小路径和。
状态转移方程：
- 边界情况：
  - 第一行（i=0, j>0）：只能从左边来 → dp[0][j] = dp[0][j-1] + grid[0][j]
  - 第一列（j=0, i>0）：只能从上面来 → dp[i][0] = dp[i-1][0] + grid[i][0]
- 通用情况（i>0, j>0）：
  - 能从左边（dp[i][j-1]）或上边（dp[i-1][j]）来，取最小值加上当前网格值 → dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
初始化：dp[0][0] = grid[0][0]（起点的路径和就是自身值）。
遍历顺序：从左到右（i 从 1 到 n）。
结果：最终 dp[m-1][n-1]（m 是行数，n 是列数）就是从左上角到右下角的最小路径和。

dp 数组计算过程：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

初始化 DP 数组：dp[0][0] = 1
填充第一行：
- j=1：dp[0][1] = dp[0][0] + 3 = 4
- j=2：dp[0][2] = dp[0][1] + 1 = 5
- 第一行 DP 结果：[1,4,5]
填充第一列：
- j=1：dp[0][1] = dp[0][0] + 3 = 4
- i=2：dp[2][0] = dp[1][0] + 4 = 6
- 第一列 DP 结果：[1,2,6]
填充其余位置：
- i=1, j=1：min(dp[0][1]=4, dp[1][0]=2) + 5 = 2+5=7 → dp[1][1]=7
- i=1, j=2：min(dp[0][2]=5, dp[1][1]=7) + 1 =5+1=6 → dp[1][2]=6
- i=2, j=1：min(dp[1][1]=7, dp[2][0]=6) + 2 =6+2=8 → dp[2][1]=8
- i=2, j=2：min(dp[1][2]=6, dp[2][1]=8) + 1 =6+1=7 → dp[2][2]=7


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;

    int m = grid.size();    // 行数
    int n = grid[0].size(); // 列数

    // 定义DP数组，dp[i][j]表示从(0,0)到(i,j)的最小路径和
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0]; // 初始化起点

    // 填充第一行（只能从左边来）
    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    // 填充第一列（只能从上面来）
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    // 填充其余位置（取左边/上边最小值 + 当前值）
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    return dp[m-1][n-1];
}

int main() {
    // 测试用例1：输出 7
    vector<vector<in>> grid1 = {{1,3,1},{1,5,1},{4,2,1}};
    cout << "Test Case 1: " << minPathSum(grid1) << endl;

    // 测试用例2：输出 12
    vector<vector<int>> grid2 = {{1,2,3},{4,5,6}};
    cout << "Test Case 2: " << minPathSum(grid2) << endl;

    return 0;
}

输出结果


Test Case 1: 7
Test Case 2: 12

五、爬楼梯（LeetCode 70）

问题描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
- 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
提示：
- 1 <= n <= 45
示例 1：
- 输入：n = 2
- 输出：2
- 解释：有两种方法可以爬到楼顶。
  - 1 阶 + 1 阶
  - 2 阶
示例 2：
- 输入：n = 3
- 输出：3
- 解释：有三种方法可以爬到楼顶。
  - 1 阶 + 1 阶 + 1 阶
  - 1 阶 + 2 阶
  - 2 阶 + 1 阶

算法解析：

确定状态：定义 dp[i] 表示到达第 i 阶台阶的不同方法数。
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
初始化：
- dp[1] = 1（1 阶台阶只有 1 种方法：爬 1 步）；
- dp[2] = 2（2 阶台阶有 2 种方法：1+1 / 2）。
遍历顺序：从左到右（i 从 1 到 n）。
结果：dp[n] 即为最终答案。

dp 数组计算过程：

输入：n=5

初始化 DP 数组：dp[0] = 1， dp[1] = 2
dp [2] = dp[2] + dp[1] = 2+1
dp [3] = dp[3] + dp[2] = 3+2
dp [4] = dp[4] + dp[3] = 5+3


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int climbStairs(int n) {
    // 处理边界情况
    if (n == 1) return 1;
    if (n == 2) return 2;

    // 定义DP数组，dp[i]表示到达第i阶的方法数
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;

    // 填充DP数组
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

int main() {
    cout << "n=2: " << climbStairs(2) << endl;  // 输出 2
    cout << "n=3: " << climbStairs(3) << endl;  // 输出 3
    cout << "n=5: " << climbStairs(5) << endl;  // 输出 8

    return 0;
}

输出结果


n=2: 2
n=3: 3
n=5: 8

返回顶部